می‌خواهیم عددهای اول از ۱ تا ۵۰ را تعیین کنیم.
ابتدا عددهای ۱ تا ۵۰ را می‌نویسیم.
حالا عددهای غیر اول را خط می‌زنیم تا عددهای اول باقی بمانند.
۱- آیا عدد ۱ را خط زدید؟ چرا؟
**بله**، عدد ۱ را خط می‌زنیم.
**چرا؟** زیرا عدد ۱ طبق تعریف، نه عددی اول است و نه عددی مرکب. عدد اول عددی است که دقیقاً دو شمارنده طبیعی متمایز (۱ و خودش) داشته باشد، در حالی که عدد ۱ فقط یک شمارنده (خودش) دارد. هدف از این روش، پیدا کردن اعداد اول است، بنابراین ۱ باید حذف شود.
۲- آیا مضرب‌های عدد ۲ را خط می‌زنید؟ چرا؟
- مضرب‌های مرکب عدد ۲ را به صورت / خط بزنید.
- مضرب‌های مرکب عدد ۳ را خط بزنید.
**بله**، مضرب‌های **مرکب** عدد ۲ را خط می‌زنیم.
**چرا؟** زیرا عدد ۲ اولین عدد اول است. خود عدد ۲ اول باقی می‌ماند، اما تمام مضرب‌های دیگر آن (مانند $۴, ۶, ۸, ...$) علاوه بر ۱ و خودشان، بر ۲ نیز بخش‌پذیر هستند، بنابراین همگی مرکب بوده و باید خط بخورند.
- **مضرب‌های مرکب ۲ که خط می‌خورند:** تمام اعداد زوج بزرگ‌تر از ۲ تا ۵۰ ($۴, ۶, ۸, ..., ۵۰$).
- **مضرب‌های مرکب ۳ که خط می‌خورند:** تمام مضرب‌های عدد ۳ بزرگ‌تر از خود ۳ ($۶, ۹, ۱۲, ..., ۴۸$). توجه کنید که برخی از این اعداد (مانند ۶ و ۱۲) قبلاً به عنوان مضرب ۲ خط خورده‌اند.
۳- آیا لازم است مضرب‌های عدد ۴ را خط بزنیم؟ خیر چرا؟ زیرا اگر عددی مضرب ۴ باشد، پیش از آن به عنوان مضرب ۲ خط خورده است.
این سوال به یک نکته کلیدی در روش غربال اراتستن اشاره دارد.
**پاسخ:** **خیر**، لازم نیست مضرب‌های عدد ۴ را به صورت جداگانه خط بزنیم.
**چرا؟** زیرا عدد ۴ یک عدد مرکب است ($۴ = ۲ \times ۲$). هر عددی که مضرب ۴ باشد، حتماً مضرب ۲ نیز هست. از آنجایی که ما در مرحله قبل تمام مضرب‌های مرکب ۲ را خط زده‌ایم، تمام مضرب‌های ۴ نیز قبلاً خط خورده‌اند. در روش غربال، ما فقط مضرب‌های اعداد **اول** را خط می‌زنیم.
۴- آیا مضرب‌های عدد ۵ را خط می‌زنید؟ چرا؟
مضرب‌های مرکب عدد ۵ را خط بزنید.
کوچک‌ترین مضرب مرکب عدد ۵، که برای اولین بار خط می‌خورد، کدام است؟
**بله**، مضرب‌های مرکب عدد ۵ را خط می‌زنیم.
**چرا؟** زیرا ۵، پس از ۲ و ۳، سومین عدد اول است و برای ادامه روش غربال باید مضرب‌های مرکب آن را حذف کنیم.
**کوچک‌ترین مضرب مرکب ۵ که برای اولین بار خط می‌خورد، کدام است؟**
کوچک‌ترین مضربی از ۵ که در این مرحله برای اولین بار خط می‌خورد، عدد **۲۵** است.
**توضیح:** مضرب‌های مرکب ۵ عبارتند از $۱۰, ۱۵, ۲۰, ۲۵, ...$ . اما:
- $۱۰ = ۵ \times ۲$ (قبلاً به عنوان مضرب ۲ خط خورده است)
- $۱۵ = ۵ \times ۳$ (قبلاً به عنوان مضرب ۳ خط خورده است)
- $۲۰ = ۵ \times ۴$ (قبلاً به عنوان مضرب ۲ خط خورده است)
اولین مضربی که شمارنده اولی کوچک‌تر از ۵ ندارد، حاصل‌ضرب ۵ در خودش یعنی $۵ \times ۵ = ۲۵$ است.
۵- آیا مضرب‌های عدد ۶ را خط می‌زنید؟ چرا؟
**خیر**، مضرب‌های عدد ۶ را به صورت جداگانه خط نمی‌زنیم.
**چرا؟** زیرا ۶ یک عدد مرکب است ($۶ = ۲ \times ۳$). هر عددی که مضرب ۶ باشد، هم مضرب ۲ و هم مضرب ۳ است. از آنجایی که ما قبلاً مضرب‌های مرکب ۲ و ۳ را به طور کامل خط زده‌ایم، تمام مضرب‌های ۶ نیز پیش از این مرحله حذف شده‌اند.
۶- آیا مضرب‌های عدد ۷ را خط می‌زنید؟ چرا؟
**بله**، مضرب‌های مرکب عدد ۷ را خط می‌زنیم.
**چرا؟** زیرا ۷، بعد از ۵، عدد اول بعدی است که در لیست ما خط نخورده است. طبق الگوریتم غربال، باید به سراغ عدد اول بعدی برویم و مضرب‌های مرکب آن را از لیست حذف کنیم تا فقط اعداد اول باقی بمانند.
۷- مضرب‌های مرکب عدد ۷ را خط بزنید. کوچک‌ترین مضرب مرکب عدد ۷، که برای اولین بار خط می‌خورد، کدام است؟
کوچک‌ترین مضرب مرکب عدد ۷ که در این مرحله برای اولین بار خط می‌خورد، عدد **۴۹** است.
**توضیح:** مضرب‌های مرکب ۷ عبارتند از $۱۴, ۲۱, ۲۸, ۳۵, ۴۲, ۴۹, ...$
- مضرب‌های $۱۴, ۲۸, ۴۲$ قبلاً به عنوان مضرب ۲ خط خورده‌اند.
- مضرب $۲۱$ قبلاً به عنوان مضرب ۳ خط خورده است.
- مضرب $۳۵$ قبلاً به عنوان مضرب ۵ خط خورده است.
اولین مضربی که شمارنده‌های اول آن کوچک‌تر از ۷ نیستند، حاصل‌ضرب ۷ در خودش یعنی $۷ \times ۷ = ۴۹$ می‌باشد. این اولین عددی است که در این مرحله حذف می‌شود.
۸- آیا مضرب‌های اعداد ۸ و ۹ و ۱۰ را خط می‌زنید؟ چرا؟
**خیر**، مضرب‌های این اعداد را به صورت جداگانه خط نمی‌زنیم.
**چرا؟** زیرا اعداد ۸، ۹ و ۱۰ همگی **مرکب** هستند.
- مضرب‌های ۸، مضرب ۲ نیز هستند.
- مضرب‌های ۹، مضرب ۳ نیز هستند.
- مضرب‌های ۱۰، مضرب ۲ و ۵ نیز هستند.
از آنجایی که ما قبلاً تمام مضرب‌های مرکب اعداد اول ۲، ۳ و ۵ را خط زده‌ایم، تمام مضرب‌های ۸، ۹ و ۱۰ نیز به طور خودکار حذف شده‌اند و نیازی به بررسی مجدد آنها نیست.
۹- اگر بخواهیم مضرب‌های عدد ۱۱ را خط بزنیم، کدام مضرب ۱۱ برای اولین بار خط خواهد خورد؟
اولین مضرب عدد ۱۱ که در روش غربال برای اولین بار خط می‌خورد، حاصل‌ضرب این عدد در خودش است:
$ ۱۱ \times ۱۱ = ۱۲۱ $
**چرا؟**
در روش غربال برای هر عدد اول $p$، اولین مضربی که خط می‌خورد $p^۲$ است. زیرا تمام مضرب‌های کوچک‌تر آن ($ ۲p, ۳p, ... $) دارای یک عامل اول کوچک‌تر از $p$ هستند و قبلاً در مراحل مربوط به آن اعداد اول کوچک‌تر (مراحل ۲، ۳ و ...) خط خورده‌اند.
برای مثال:
- $ ۱۱ \times ۲ = ۲۲ $ (مضرب ۲ بوده و قبلاً خط خورده)
- $ ۱۱ \times ۳ = ۳۳ $ (مضرب ۳ بوده و قبلاً خط خورده)
- $ ۱۱ \times ۵ = ۵۵ $ (مضرب ۵ بوده و قبلاً خط خورده)
- $ ۱۱ \times ۷ = ۷۷ $ (مضرب ۷ بوده و قبلاً خط خورده)
بنابراین، اولین مضربی از ۱۱ که شمارنده اولی کوچک‌تر از ۱۱ ندارد، خود ۱۲۱ است.
۱۰- به این ترتیب، آیا لازم است مضرب‌های عدد ۱۱ را خط بزنیم؟
**خیر**، برای پیدا کردن اعداد اول تا ۵۰، لازم نیست مضرب‌های عدد ۱۱ را خط بزنیم.
**چرا؟**
دو دلیل برای این موضوع وجود دارد:
۱. همان‌طور که در سوال قبل مشخص شد، اولین مضرب ۱۱ که ممکن بود در این مرحله خط بخورد، عدد **۱۲۱** است. از آنجایی که ما فقط اعداد تا **۵۰** را بررسی می‌کنیم و $ ۱۲۱ > ۵۰ $ است، هیچ مضربی از ۱۱ در محدوده ما برای خط زدن باقی نمانده است.
۲. یک قانون کلی در روش غربال وجود دارد: برای پیدا کردن اعداد اول تا عدد $n$، کافی است مضرب‌های اعداد اولی را خط بزنیم که از $ \sqrt{n} $ کوچک‌تر یا مساوی باشند. در اینجا $ n=۵۰ $ است و $ \sqrt{۵۰} \approx ۷.۰۷ $ می‌باشد. بنابراین، ما فقط باید مضرب‌های اعداد اول $۲, ۳, ۵, ۷$ را بررسی کنیم و نیازی به بررسی مضرب‌های ۱۱ نیست.
۱۱- آیا عددهای باقی‌مانده، اول هستند؟
**بله**، تمام اعدادی که پس از پایان مراحل غربال خط نخورده باقی می‌مانند، اعداد اول هستند.
**چرا؟**
روش غربال اراتستن به طور منظم تمام اعداد غیر اول (یعنی عدد ۱ و اعداد مرکب) را حذف می‌کند. عددی که در این فرآیند باقی می‌ماند، به این معنی است که بر هیچ عدد اول کوچک‌تر از خودش بخش‌پذیر نبوده است. این دقیقاً تعریف یک عدد اول است.
**اعداد اول ۱ تا ۵۰ که در نهایت باقی می‌مانند عبارتند از:**
$ \{ ۲, ۳, ۵, ۷, ۱۱, ۱۳, ۱۷, ۱۹, ۲۳, ۲۹, ۳۱, ۳۷, ۴۱, ۴۳, ۴۷ \} $
